package com.taobao.wms;





/*
Java版 泛型动态Array

实现一个支持动态扩容的数组
实现一个大小固定的有序数组，支持动态增删改操作
实现两个有序数组合并为一个有序数组
*/
public class MyArray<T>{
	T[] data; // 存储值
	int size; // 元素个数
	
	@SuppressWarnings("unchecked")
	public MyArray(int initialCapacity){ // 构造方法
		if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
		this.data = (T[]) new Object[initialCapacity];
		this.size = 0;
	}
	public MyArray(){ // 无参构造方法
		this(10); // 默认10的数组容量
	}
	public int getCapacity(){ // 获取数组容量 "数组容量"跟"元素个数"不是一个概念
		return this.data.length;
	}
	
	public int count(){ // 获取当前元素个数
		return this.size;
	}
	
	public boolean isEmpty(){// 判断数组是否为空
		return this.size == 0;
	}
	
	public void set(int index, T e){ //修改 index 位置的元素
		checkIndex(index);
		this.data[index] = e;
	}
	
	public T get(int index){ // 获取对应 index 位置的元素
		checkIndex(index);
		return this.data[index];
	}
	
	public boolean contains(T e){ // 查看数组是否包含元素e
		for (int i = 0; i < this.size; i++) {
			if(e == this.data[i] || e.equals(this.data[i])){
				return true;
			}
		}
		return false;
	}
	// 规定不能存放null值
	public int find(T e){ // 获取对应元素的下标, 未找到，返回 -1
		if(e == null){
			return -1;
		}
		for (int i = 0; i < this.size; i++) {
			if(e == this.data[i] || e.equals(this.data[i])){
				return i;
			}
		}
		return -1;
	}
	public void add(T e){ // 添加元素
		if(this.size == this.data.length){
			resize(2 * this.data.length);
		}
		this.data[this.size] = e;
		this.size++;
	}
	
	// TODO
	public void add(int index, T e){ // 在 index 位置，插入元素e, 时间复杂度 O(m+n)
		checkIndex(index);
		
		// 如果当前数组数量等于数组容量,则扩容2倍
		if(this.size == this.data.length){
			resize(2 * this.data.length);
		}
		/// 假设原数组为 2 4 5 6 8
		/// 传入参数为 index=3 e=7
		/// 最后输出结果为 2 4 5 7 6 8		
		for (int i = size - 1; i >= index; i--) {
		// 参数i = size -1 = 4
		// i>=index 类比 4 >= 3
		// 执行代码 data[5] = data[4]  最后得到2 4 5 6 8 8 
			data[i + 1 ] = data[i];
		// i = 4 -1 = 3
		// 3 >= 3
		// data[4] = data[3]  2 4 5 6 6 8
		// i = 3 -1 = 2
		// 2 >= 3  判断为false 跳出去 2 4 5 6 6 8
		}		
		data[index] = e;
		size++;
	}
	
	public void addFirst(T e){ // 向数组头插入元素
		this.add(0, e);
	}
	
	public void addLast(T e){ // 向数组尾插入元素
		this.add(this.size, e);
	}
	
	public T remove(int index){ // 删除 index 位置的元素，并返回元素
		checkIndexForRemove(index);
		/// 假设原数组为 2 4 5 6 8
		/// 传入参数为 index=3
		/// 最后输出结果为 2 4 5 8
		T temp = data[index];
		for (int i = index + 1; i < size; i++) {
			// 挪位置	
			// i = 4
			// 4 < 5
			// data[3] = data[4] 2 4 5 8 8
			data[i-1] = data[i];
			
			// i = 5
			// 5 < 5 不成立
			// data[2] = data[3] 2 4 5 8 8
		}
		//size = 5 - 1
		size--;
		//2 4 5 8 8
		//size = 4
		//data[4] = null
		data[size] = null;
		//缩容量
		if (size == data.length / 4 && data.length / 2 != 0) {
            resize(data.length / 2);
        }
		return temp;
	}
	
	public T removeFirst(){ // 删除第一个元素
		return this.remove(0);
	}
	
	public T removeLast(){ // 删除末尾元素
		return this.remove(this.size - 1);
	}
	
	public void removeElement(T e){ // 从数组中删除指定元素
		int index = find(e);
		if(index != -1){
			remove(index);
		}
	}
	
	public String toString(){ //
		StringBuilder builder = new StringBuilder();
        builder.append(String.format("Array size = %d, capacity = %d \n", size, data.length));
        builder.append('[');
        for (int i = 0; i < size; i++) {
            builder.append(data[i]);
            if (i != size - 1) {
                builder.append(", ");
            }
        }
        builder.append(']');
        return builder.toString();
	}
	
	@SuppressWarnings("unchecked")
	public void resize(int capacity){ // 扩容方法，时间复杂度 O(n)
		T[] newObjArr = (T[]) new Object[capacity];
		for (int i = 0; i < this.size; i++) {
			newObjArr[i] = this.data[i];
		}
		this.data = newObjArr;
	}
	public void checkIndex(int index){ // 校验角标是否越界
		if (index < 0 || index > this.size)
			throw new ArrayIndexOutOfBoundsException("数组角标越界");
	}
	
	public void checkIndexForRemove(int index){ // 校验角标是否越界
		if (index < 0 || index >= this.size)
			throw new ArrayIndexOutOfBoundsException("数组角标越界");
	}
	
	public void insert(int index, T e){
		// 校验
		checkIndex(index);
		
		// 是否扩容
		if(this.size == this.data.length){
			this.resize(2 * this.data.length);
		}
		
		// 如果是最后面追加
		if(index == this.size){
			this.add(e);
			return;
		}
		
		// 挪位置,赋值
		/*
		 *  [2, 3, 5, 6, 8, null, null, null, null, null]
			[2, 3, 5, 6, 8, 8, null, null, null, null]
			[2, 3, 5, 6, 6, 8, null, null, null, null]
			[2, 3, 5, 7, 6, 8, null, null, null, null]
		 **/
		// 关键是由前往后开始赋值 插入就是多开辟一个位置
		// 当 i < index 的时候, 那就是找到了可赋值的位置
 		for (int i = this.size - 1; i >= index; i--) {
			this.data[i + 1] = this.data[i];
		}
		
		// 赋值
		this.data[index] = e;
		
		// 增加数组元素个数
		this.size++;
		
	}
	
	public T delete(int index){ // 删除
		// 校验
		checkIndexForRemove(index);
		
		// 先赋值给临时变量
		T temp = this.data[index];
		
		// 挪位置
		/*
		 * 参数 3
		 * [2, 3, 5, 6, 8]
		   [2, 3, 5, 8, 8]
		   [2, 3, 5, 8, null]
		 */
		
		// 参数为index=2
		// (index+1=3) < 5 
		// data[2] = data[3]
		// [2, 3, 6, 6, 8]
		
		// 4 < 5 
		// data[3] = data[4]
		// [2, 3, 6, 8, 8]
		
		// 5 < 5 
		// [2, 3, 6, 8, 8]
		
		// 由后往前开始赋值 删除就是减少一个位置
		for (int i = index + 1 ; i < this.size; i++) {
			this.data[i - 1] = this.data[i];
		}
		// 减小数组元素个数
		this.size--;
		// 删除元素
		this.data[this.size] = null;
		
		// 缩容
		if(this.size == this.data.length / 4 && this.data.length / 2 != 0){
			resize(this.data.length / 2);
		}
		
		// 返回
		return temp;
	}

	
	
	public static void main(String[] args) {
		MyArray<Integer> arr = new MyArray<>(5);
		arr.add(0, 2);
		arr.add(1, 3);
		arr.add(2, 5);
		arr.add(3, 6);
		arr.add(4, 8);
		System.out.println(arr);
		arr.delete(1);
		System.out.println(arr);
	}
	
}
